package com.leetcode;

import com.leetcode.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 113. 路径总和 II
 * 递归, 从底到顶的思维
 *
 * @author fy
 * @date 2022/4/24 17:52
 */
public class Solution113_2 {

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        if (isLeafNode(root)) {
            if (root.val == targetSum) {
                // 如果到叶子节点了, 则创建一个空的list将该节点添加进去然后返回
                List<Integer> res = new ArrayList<>();
                res.add(root.val);
                list.add(res);
            }
            return list;
        }
        // 找到左右节点的路径, 将当前节点加到最前面然后将整个列表添加进来
        List<List<Integer>> leftPath = pathSum(root.left, targetSum - root.val);
        List<List<Integer>> rightPath = pathSum(root.right, targetSum - root.val);
        leftPath.addAll(rightPath);
        if (!leftPath.isEmpty()) {
            for (List<Integer> item : leftPath) {
                // 这里将新的元素添加到第一个位置就可以
                //List<Integer> res = new ArrayList<>();
                //res.add(root.val);
                //res.addAll(item);
                //list.add(res);
                item.add(0, root.val);
                list.add(item);
            }
        }
        return list;
    }

    private boolean isLeafNode(TreeNode node) {
        return node != null && node.left == null && node.right == null;
    }

}
